#include <iostream>
#include <vector>
using namespace std;

int max_value_recur(vector<int> &w, vector<int> &c, vector<int> &p, int n, int m)
{
        if(n == 0 || m == 0){
                return 0;
        }

        int max_value = max_value_recur(w, c, p, n - 1, m);
        for(int i = 1; (p[n] == 0 || i <= p[n]) && w[n] * i <= m; i++){
                max_value = max(max_value, max_value_recur(w, c, p, n - 1, m - w[n] * i) + c[n] * i);
        }
        return max_value;
}

int max_value_dp(vector<int> &w, vector<int> &c, vector<int> &p, int m)
{
        int n = w.size() - 1;
        vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));

        for(int i = 1; i <= n; i++){
                for(int j = 1; j <= m; j++){
                        dp[i][j] = dp[i - 1][j];
                        for(int k = 1; (p[i] == 0 || k <= p[i]) && w[i] * k <= j; k++){
                                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i] * k] + c[i] * k);
                        }
                }
        }
        return dp.back().back();
}

int main()
{
        int m, n;
        cin>>m>>n;
        vector<int> w(n + 1, 0), c(w), p(w);
        for(int i = 1; i <= n; i++){
                cin>>w[i]>>c[i]>>p[i];
        }
        cout<<max_value_dp(w, c, p, m)<<endl;
        return 0;
}